package puzzle.projecteuler.p300;

import java.util.ArrayList;
import java.util.List;

public class Problem209A {

	/**
	 *     τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0 
	 * <=> τ(a, b, c, d, e, f) = 0 or τ(b, c, d, e, f, a XOR (b AND c)) = 0
	 * 我们把a,b,c,d,e,f映射到二进制整数(abcdef)，
	 * 条件就变成了对0~63之间的任何整数X = (abcdef)，都有
	 * τ(X) = 0 or τ(Y) = 0, 其中Y = (bcdefg), g = a XOR (b AND c)
	 * 
	 * 这样0~63的数可以分成若干组，每组数形成一个环，环中每个数或0或1，满足相邻的两个数中至少有一个0。
	 * 
	 * 假设Fibonacci数列定义如下F0=0, F1=F2=1, F_(n) = F_(n-1) + F_(n-2)
	 * 那么长度是n的满足条件的环，一共有F_(n-1) + F_(n+1)个
	 * 
	 * 利用这些结论，很容易得到本题的结果。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long count = 1;
		List<Integer> all = new ArrayList<Integer>();
		for (int i = 0; i < 64; i ++) all.add(i);
		while (!all.isEmpty()) {
			int seed = all.get(0);
			List<Integer> cycle = findCycle(seed);
			all.removeAll(cycle);
			
			int n = cycle.size();
			count *= A(n);
		}
		System.out.println(count);
	}

	private static List<Integer> findCycle(int n) {
	
		List<Integer> tmp = new ArrayList<Integer>();
		tmp.add(n);
		int m = n;
		do {
			m = next(m);
			if (tmp.contains(m)) {
				return tmp;
			} else {
				tmp.add(m);
			}
		} while (true);
	}
	
	private static int next(int n) {

		int a = (n>>5)%2;
		int b = (n>>4)%2;
		int c = (n>>3)%2;
		int d = (n>>2)%2;
		int e = (n>>1)%2;
		int f = n%2;
		int g = a^(b&c);
		
		return (b<<5)+(c<<4)+(d<<3)+(e<<2)+(f<<1)+g;
	}
	
	private static long F(long n) {
		
		long a = 0;
		long b = 1;
		while (n > 0) {
			long x = a;
			a = b;
			b = x+a;
			n --;
		}
		return a;
	}
	
	private static long A(int n) {
		return F(n-1) + F(n+1);
	}
}
